package leetcode_1301_1400;

import java.util.HashMap;
import java.util.Map;

public class LeeCode_1326 {
    public static void main(String[] args) {
        System.out.println(minTaps(3, new int[]{0, 0, 0, 0}));
    }
    private static int minTaps(int n, int[] ranges) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < ranges.length; i++) {
            int d = ranges[i];
            int l = Math.max(i - d, 0), r = Math.min(n, i + d);
            for (int j = l; j <= r; j++) {
                map.put(j, Math.max(map.getOrDefault(j, 0), r));
            }
        }
        int ans = 0, loc = 0;
        while (loc < n){
            if (!map.containsKey(loc)){
                return -1;
            }
            if (map.get(loc) == loc)
                return -1;
            loc = map.get(loc);
            ans++;
        }
        return ans;
    }
}